﻿#region Copyright and Licensing Notice
// Copyright (C) 2011 Steven Bosnick
// 
// This program is open source software; you can redistribute it 
// and/or modifiy it under the terms of the Eclipse Public License,
// version 1.0.
// 
// This program is distributed in the hope that it will be useful, 
// but WITHOUT ANY WARRANTY; without even the implied
// warranty of MERCHANTABILITY or FITNESS FOR A 
// PARTICULAR PURPOSE. See the Eclipse Public License for more
// details.
// 
// You should have received a copy of the Eclipse Public License 
// along with this program; if not, you can find a copy at
// "http://www.opensource.org/licenses/eclipse-1.0.php".
#endregion
using System;
using BitwiseOre.SharedMemory.Core.Common;

namespace BitwiseOre.SharedMemory.Core.Primatives
{
    /*
     * The implementation of this non-blocking thread-safe queue is based on D. Fober, Y. Orlarey. S. Letz, "Lock-Free
     * Techniques for Concurrent Access to Shared Objects", (Grame - Centre National de Création Musicale, Sept. 30
     * 2003). The pseudo code in the methods below is taken from this paper.
     */
    internal sealed class IndexQueue : ISharedObjectInit, IIndexQueue
    {
        private const int DummyIndex = CountedIndex.MaxIndex - 1;
        private readonly IIndexQueueLayout _control;
        private readonly IIntArray _next;

        public IndexQueue(IIndexQueueLayout control, IIntArray next)
        {
            _control = control;
            _next = next;
        }

        void ISharedObjectInit.InitializeNew()
        {
            #region Pseudocode
            /*
             * fifo-init (ff: pointer to fifo, dummy: pointer to dummy cell)
             *      dummy->next = NULL            # makes the cell the only cell in the list
             *      ff->head = ff->tail = dummy   # both head and tail point to the dummy cell
             */
            #endregion

            _control.Dummy = QueueConstants.NullIndex;
            _control.Head = new CountedIndex(DummyIndex, 0);
            _control.Tail = new CountedIndex(DummyIndex, 0);
        }

        void ISharedObjectInit.InitializeExisting()
        {
        }

        public void Enqueue(int index)
        {
            if (index < 0 || index > QueueConstants.MaxQueueIndex) 
                throw new ArgumentOutOfRangeException("index");

            EnqueueCore(index);
        }

        private void EnqueueCore(int index)
        {
            #region Pseudocode
            /*
             * fifo-push (ff: pointer to fifo, cl: pointer to cell)
             * E1 cl->next = ENDFIFO(ff)                   # set the cell next pointer to end marker
             * E2 loop                                     # try until enqueue is done
             * E3:   icount = ff->icount                   # read the tail modification count
             * E4:   tail = ff->tail                       # read the tail cell
             * E5:   if CAS (&tail->next, ENDFIFO(ff), cl) # try to link the cell to the tail cell
             * E6:       break;                            # enqueue is done, exit the loop
             * E7:   else                                  # tail was not pointing to the last cell, try to set
             *                                                             # tail to the next cell
             * E8:       CAS2 (&ff->tail, tail, icount, tail->next, icount+1)
             * E9:   endif
             * E10: endloop
             * E11: CAS2 (&ff->tail, tail, icount, cl, icount+1)   # enqueue is done, try to 
             *                                                     # set tail to the enqueued cell
             */
            #endregion


            this[index] = QueueConstants.NullIndex;
            CountedIndex tail;
            while (true)
            {
                tail = _control.Tail;
                if (Cas(tail.Index, QueueConstants.NullIndex, index))
                {
                    break;
                }
                _control.CasTail(tail, new CountedIndex(tail.Index, tail.Count + 1));
            }
            _control.CasTail(tail, new CountedIndex(index, tail.Count + 1));
        }

        public int Dequeue()
        {
            #region Pseudocode
            /*
             * fifo-pop (ff: pointer to fifo): pointer to cell
             * D1: loop                                                            # try until dequeue is done
             * D2:     ocount = ff->ocount                                         # read the head modification count
             * D3:     icount = ff->icount                                         # read the tail modification count
             * D4:     head = ff->head                                             # read the head cell
             * D5:     next = head->next                                           # read the next cell
             * D6:     if ocount == ff->oc                                         # ensures that next is a valid pointer
             *                                                                     # to avoid failure when reading next value
             * D7:         if head == ff->tail                                     # is queue empty or tail falling behind ?
             * D8:             if next == ENDFIFO(ff)                              # is queue empty ?
             * D9:                 return NULL                                     # queue is empty: return NULL
             * D10:            endif
             *                                                                     # tail is pointing to head in a non empty queue, 
             *                                                                     # try to set tail to the next cell
             * D11:            CAS2 (&ff->tail, head, icount, next, icount+1)
             * D12:        else if next <> ENDFIFO(ff)                             # if we are not competing on the dummy next
             * D13:            if CAS2 (&ff->head, head, ocount, next, ocount+1)   # try to set head to the next cell
             * D14:                break                                           # dequeue done, exit the loop
             * D15:            endif
             * D16:        endif
             * D17: endloop
             * D18: if head == dummyCell                                           # check wether we’re trying to pop the dummy cell
             * D19:    fifo-push(ff,head)                                          # this is the dummy cell: push it back to the fifo
             * D20:    head = fifo-pop(ff)                                         # and pop a cell again
             * D21: endif
             * D22: return head                                                    # return head cell
             */
            #endregion

            CountedIndex head;
            while (true)
            {
                head = _control.Head;
                var tail = _control.Tail;
                var next = this[head.Index];
                if (head.Count != _control.Head.Count) continue;
                if (head.Index == _control.Tail.Index)
                {
                    if (next == QueueConstants.NullIndex)
                    {
                        return QueueConstants.NullIndex;
                    }
                    _control.CasTail(tail, new CountedIndex(next, tail.Count + 1));
                }
                else if (next != QueueConstants.NullIndex)
                {
                    if (_control.CasHead(head, new CountedIndex(next, head.Count + 1)))
                    {
                        break;
                    } 
                }
            }
            if (head.Index == DummyIndex)
            {
                EnqueueCore(head.Index);
                return Dequeue();
            }
            return head.Index;
        }

        private int this[int index]
        {
            get { return index == DummyIndex ? _control.Dummy : _next[index]; }
            set 
            {
                if (index == DummyIndex)
                {
                    _control.Dummy = value;
                }
                else
                {
                    _next[index] = value;        
                }
            }

        }

        private bool Cas(int index, int comparand, int value)
        {
            return index == DummyIndex
                       ? _control.CasDummy(comparand, value)
                       : _next.InterlockedCompareExchange(index, comparand, value);
        }
    }
}